\section{Multivariate Polynomials}

% Polynomials are the moving spirit behind Gröbner bases.

\begin{df}
  Let $\alpha = \left( \alpha_1, \ldots, \alpha_n \right)$ be an $n$-tuple of non-negative integers.
  A \textbf{monomial} in $x_1, \ldots, x_n$ is a product of the form \[\prod_{i=1}^n
    x_i^{\alpha_i} = x_1^{\alpha_1} \cdot x_2^{\alpha_2} \cdots x_n^{\alpha_n}.\]
\end{df}

Let us simplify the notation by setting \[x^\alpha = \prod_{i=1}^n x_i^{\alpha_i}.\] The
\textbf{total degree} of a monomial $x^\alpha$ is the sum $\sum_{i=1}^n \alpha_i.$ We
simplify the notation again an let $\lvert x^\alpha \rvert$ denote the total degree
of $x^\alpha$. We will call the symbols $x_1, \ldots, x_n$ indeterminates or variables,
depending on which context we will need to emphasize. Note that $x^\alpha = 1$ when
$\alpha = \left( 0, \ldots, 0 \right)$ and also when $\lvert x^\alpha \rvert = 0$. Also note
that any monomial is fully determined by $\alpha$.

\begin{df}
  Let $x^\alpha$ be a monomial and let $K$ be a field. A \textbf{term} with a
  non-zero \textbf{coefficient} $c_\alpha \in K$ is the product $c_\alpha x^\alpha$.
\end{df}

\begin{df}
  A \textbf{polynomial} $f$ with coefficients in a field $K$ is a finite sum of
  terms in the form \[f = \sum_\alpha c_\alpha \cdot x^\alpha, \quad c_\alpha \in K.\] The zero polynomial will
  be denoted $0$.
\end{df}

\begin{df}
  Let $f = \sum c_\alpha x^\alpha \ne 0$ be a non-zero polynomial. The \textbf{total
    degree} of $f$, denoted deg$\left( f \right)$, is the maximum $\lvert x^\alpha
  \rvert$ such that the corresponding coefficient $c_\alpha$ is nonzero. The degree
  of $0$ is undefined.
\end{df}

The set of all polynomials in $x_1, \ldots, x_n$ with coefficients in a field $K$
will be denoted $K\!\left[ x_1, \ldots, x_n \right]$. When the particular
indeterminates are of no relevance, we will denote the set by
$K\!\left[\mathbf{x} \right]$ for short. We will also employ the standard
letters $x, y$ and $z$ instead of $x_1, x_2$ and $ x_3$ when we discuss
illustrative polynomials.

Let $f,g \in K\!\left[ \mathbf{x} \right]$ be polynomials. We say that $f$
\emph{divides} $g$ if $g = fh$ for some polynomial $h \in K\!\left[ \mathbf{x}
\right]$. One can show that the set $K\!\left[ \mathbf{x} \right]$ satisfies all
of the ring axioms under standard polynomial addition and multiplication. We
will therefore refer to $K\!\left[ \mathbf{x} \right]$ as a \emph{polynomial
  ring}. Not all polynomials in this ring have their multiplicative inverses,
e.g., even the elementary polynomial $x_1$ does not have its multiplicative
inverse and so $K\!\left[ \mathbf{x} \right]$ does not form a field. A proof
that $K\!\left[ \mathbf{x} \right]$ forms a ring can be found in
\cite[Chapher~2]{gb}, the authors also provide a broader outlook on polynomials
by defining them in a more abstract way.

\begin{df}
  Let $\set*{f_1, \ldots, f_s} \subset K\!\left[ \mathbf{x} \right]$ be a set of
  polynomials. Then we set \[\langle f_1, \ldots, f_s \rangle = \set*{\sum_{i=1}^s
      h_if_i~\bigg|~h_1, \ldots, h_s \in K\!\left[ \mathbf{x} \right]}.\]
\end{df}

\begin{lm}
  If $\set*{f_1, \ldots, f_s} \subset K\!\left[ \mathbf{x} \right]$ is a set of
  polynomials, then $\langle f_1, \ldots, f_s \rangle$ is an ideal of $K\!\left[ \mathbf{x}
  \right]$.
\end{lm}

\begin{p}
  Assume $f = \sum_{i=1}^s p_if_i$ and $g = \sum_{i=1}^s q_if_i$ are polynomials, and
  let also $h \in K\!\left[ \mathbf{x} \right]$ be a polynomial. Then the
  equations
  \begin{align*}
    f + g &= \sum_{i=1}^s \left( p_i + q_i \right) f_i \text{\quad and} \\
       hf &= \sum_{i=1}^s \left( hp_i \right) f_i
  \end{align*}
  show that $\langle f_1, \ldots, f_s \rangle$ meets the criteria for being an ideal of
  $K\!\left[ \mathbf{x} \right]$.
\end{p}

\begin{df}
  Let $\set*{f_1, \ldots, f_s} \subset K\!\left[ \mathbf{x} \right]$ be a set of
  polynomials and let $I$ be an ideal such that $I = \langle {f_1, \ldots, f_s} \rangle$. The set
  $\set*{f_1, \ldots, f_s}$ is a \textbf{basis} of $I$. We will also call $\langle {f_1, \ldots,
    f_s} \rangle$ the \textbf{ideal generated by} $\set*{f_1, \ldots, f_s}$.
\end{df}

Remark \ref{ideal_re} provides an intuitive view of ideals through modular
arithmetic. Another analogy comes from linear algebra where the definition of
subspaces can be likened to the definition of ideals of polynomial rings. Both
are closed under addition. Subspaces are closed under multiplication by scalars
while ideals of polynomial rings are closed under multiplication by polynomials.
An ideal generated by a set of polynomials also shares similar properties with a
span generated by a set of vectors, which is a structure similar to subspaces as
well.

\begin{df}
  Let $K$ be a field and $n$ a positive integer. The $n$-dimensional
  \textbf{affine space} over $K$ is the set \[K^n = \set*{\left( a_1, \ldots, a_n
      \right)\ |\ a_1, \ldots, a_n \in K}.\] 
\end{df}

\begin{re} \label{poly_re}
  A polynomial $f \in K\!\left[ x_1, \ldots, x_n \right]$ can be regarded as a function
  $f : K^n \mapsto K$ that takes in points in the affine space $K^n$ and produces
  elements of the field $K$.
\end{re}

\begin{df}
  Let $K^n$ be an affine space and let $f = f\!\left( x_1, \ldots, x_n \right) \in
  K\!\left[ x_1, \ldots, x_n \right]$ be a polynomial. The \textbf{zero point} of $f$
  is a point $\left( a_1, \ldots, a_n \right) \in K^n$ such that $f\!\left( a_1, \ldots, a_n
  \right) = 0$.
\end{df}

\begin{df}
  Let $\set*{f_1, \ldots, f_s} \subset K\!\left[ x_1, \ldots, x_n \right]$ be a set of
  polynomials and $K^n$ an affine space. The \textbf{affine variety} $V\!\left(
    f_1, \ldots, f_s \right)$ defined by $\set*{f_1, \ldots, f_s}$ is the set \[V\!\left(
      f_1, \ldots, f_s \right) = \set*{\left( a_1, \ldots, a_n \right) \in
      K^n~\Big|~f_i\!\left( a_1, \ldots, a_n \right) = 0 \text{ for all } 1 \le i \le
      s}\] of all zero points of all the polynomials in $\set*{f_1, \ldots, f_s}$.
\end{df}

Solving an equation that can be expressed as a polynomial in multiple variables
can be seen as finding the zero points of the corresponding polynomial. Affine
varieties generalize this notion to systems of polynomial equations. Considering
remark \ref{poly_re}, we may also see varieties as geometric objects, which is briefly
illustrated by the following example:

\begin{e}
  Consider the real coordinate space $\mathbb{R}^2$ and the polynomial $f =
  f\!\left( x^2 + y^2 - 1 \right)$. The variety $V\!\left( f \right)$ is the
  unit circle centered at the origin.
\end{e}

We will use the following lemma to show that a given ideal is contained in
another one. This is useful for proving the equality of two ideals in example
\ref{ideal_e}.

\begin{lm}
  \label{ideal_lm}
  Let $I \subseteq K\!\left[ \mathbf{x} \right]$ be an ideal, and let $\set*{f_1, \ldots,
    f_s} \subset K\!\left[ \mathbf{x} \right]$ be a set of polynomials. Then $\langle f_1,
  \ldots, f_s \rangle \subseteq I$ if and only if $\set*{f_1, \ldots, f_s} \subseteq I$.
\end{lm}

\begin{ps}
  \begin{itemize}
  \item[$\implies$] Assume $\langle {f_1, \ldots, f_s} \rangle \subseteq I$. Each $f_i \in \set*{f_1, \ldots,
      f_s}$ can be constructed as follows: $f_i = 0 \cdot f_1 + \cdots + 1 \cdot f_i + \cdots + 0
    \cdot f_s$, and hence $\set*{f_1, \ldots, f_n} \subseteq I$.
  \item[$\impliedby$] Assume $\set*{f_1, \ldots, f_n} \subseteq I$ and choose any $f \in \langle
    {f_1, \ldots, f_s} \rangle$ so that $f = h_1f_1 + \cdots + h_sf_s$ where each $h_i \in
    K\!\left[ \mathbf{x} \right]$. We see that $f \in I$ since $I$ is an
    ideal and so $\langle {f_1, \ldots, f_s} \rangle \subseteq I$. \qedhere
  \end{itemize}
\end{ps}

\begin{e}
  \label{ideal_e}
  Consider the ideals $\langle {x, y} \rangle$ and $\langle {x + y, x - y} \rangle$ in the polynomial
  ring $\mathbb{Q}\!\left[ x, y \right]$. We will show that these two ideals are
  equal so that $\langle {x, y} \rangle = \langle {x + y, x - y} \rangle$.

  We see that $x + y \in \langle {x, y} \rangle$ and $x - y \in \langle {x, y} \rangle$, so by lemma
  \ref{ideal_lm}, $\langle {x + y, x - y} \rangle \subseteq \langle {x, y} \rangle$. Similarly, both $x =
  \frac{1}{2}\!\left( x + y \right) + \frac{1}{2}\!\left( x - y \right)$ and
  $y = \frac{1}{2}\!\left( x + y \right) - \frac{1}{2}\!\left( x - y \right)$
  are in $\langle {x + y, x - y} \rangle$ so that by lemma \ref{ideal_lm}, $\langle {x, y} \rangle \subseteq \langle
  {x + y, x - y} \rangle$ and the equality follows.
\end{e}

\begin{pr}
  \label{ideal_pr}
  If $\set*{f_1, \ldots, f_s}$ and $\set*{g_1, \ldots, g_t}$ are two bases of the same
  ideal in $K\!\left[ x_1, \ldots, x_n \right]$, so that $\langle f_1, \ldots, f_s \rangle =
  \langle g_1, \ldots, g_t \rangle$, then $V\!\left( f_1, \ldots, f_s \right) = V\!\left(g_1, \ldots, g_t
  \right)$. 
\end{pr}

\begin{p}
  \sloppy Choose any $\left( a_1, \ldots, a_n \right) \in V\!\left( f_1, \ldots, f_s
  \right)$. We know that all polynomials in $\set*{f_1, \ldots, f_s}$ are equal to
  zero at $\left( a_1, \ldots, a_n \right)$. Now choose any $g \in \langle {g_1, \ldots, g_t} \rangle$.
  Since $\langle {g_1, \ldots, g_t} \rangle = \langle {f_1, \ldots, f_s} \rangle$, we can write $g = \sum_{i=1}^s h_i
  f_i$, $h_i \in K\!\left[x_1, \ldots, x_n \right]$. Then $g\!\left( a_1, \ldots, a_n
  \right) = \sum_{i=1}^s h_i\!\left( a_1, \ldots, a_n \right) \cdot f_i\!\left( a_1, \ldots, a_n
  \right) = 0,$ which shows that $\left( a_1, \ldots, a_n \right) \in V\!\left( g_1, \ldots,
    g_t \right)$, which means that $V\!\left( f_1, \ldots, f_s \right) \subseteq V\!\left(
    g_1, \ldots, g_t \right)$. The opposite inclusion can be proved in the same way.
\end{p}

Example \ref{ideal_e} shows that an ideal may have multiple different bases
while proposition \ref{ideal_pr} reveals that a variety is actually determined
by the ideal generated by its basis and not by the basis itself.

A system of multivariate equations can be seen as an ideal basis. Proposition
\ref{ideal_pr} then gives us a potential ability to change the original system
to another one while keeping the exact same solution set. We will model our
cipher as system of polynomial equations and then we will transform this system
into a new one which will be solvable in linear time. We will show that a
Gröbner basis is the new system and that the transformation will be the most
demanding part of the computation as regards both time and memory.
